//
// Created by aquawius on 25-3-12.
//
#ifndef SHELL_SORT
#define SHELL_SORT

#include <algorithm>
#include <iostream>
#include <random>

// 希尔排序，

// 不稳定的算法
// 希尔排序（直接插入排序的优化） 希尔排序是将数据分组，将每一组进行插入排序。 每一组排成有序后，最后整体就变有序了。

void shellSort(int arr[], int size)
{
    int gap = size;
    while (gap > 1) {
        gap /= 2;
        // 从这里开始就是加入了gap值的插入排序了
        for (int i = gap; i < size; i++) {
            int val = arr[i];
            int j = i - gap;
            // j每次-gap个位置
            for (; j >= 0; j -= gap) {
                if (arr[j] > val) {
                    // j下标的值大，将j下标的值放到j变量加上一个gap的位置上
                    arr[j + gap] = arr[j];
                } else {
                    // j下标的值较小，j下标的值要直接放到j变量加上一个gap的位置上
                    break;
                }
            }
            // 此时j下标的值是负数了，将tmp的值放到j变量加上一个gap的位置上
            arr[j + gap] = val;
        }
    }
}

int main(int argc, char** argv)
{
    std::random_device rd;
    std::default_random_engine engine(rd());
    std::uniform_int_distribution<int> dis(0, 100);

    const auto arr = new int[100];

    for (int i = 0; i < 100; ++i) {
        arr[i] = dis(engine);
    }

    std::for_each(arr, arr + 100, [](const int a) { std::cout << a << ' '; });

    std::cout << std::endl;

    shellSort(arr, 100);

    std::for_each(arr, arr + 100, [](const int a) { std::cout << a << ' '; });

    // 释放动态分配的内存
    delete[] arr;

    return 0;
}

#endif // SHELL_SORT